Today’s Agenda

  • Hausdorff Distance
  • Gromov–Hausdorff Distance
  • Hasudorff vs Gromov–Hausdorff
  • The curious case of the circle
  • Lower bounds
    • Riemannian manifolds
    • metric graphs
  • Future work

Definition 1 (Directed Hausdorff Distance) For two subsets compact \(X,Y\subset\mathbb R^n\), their directed Hausdorff distance is \[ \vec{d}_H(X,Y)=\inf\big\{r\geq0\mid X\subset \bigcup_{y\in Y} B(y,r)\big\}. \]

All metric properties but symmetry.

Definition 2 (Hausdorff Distance)  

\[\begin{aligned} d_H(X,Y) &=\max\big\{\vec{d}_H(X,Y),\vec{d}_H(Y,X)\big\} \\ &=\sup\big\{r\geq0 \mid X\subset \bigcup_{y\in Y} B(y,r)\text{ and }Y\subset \bigcup_{x\in X} B(x,r)\big\}. \end{aligned}\]

Why Only Euclidean Subsets?

Definition 3 (Hausdorff Distance) Let \((Z,d)\) be a metric space and \(X, Y\subset Z\) compact subsets. \[ d^Z_H(X,Y)=\sup\big\{r\geq0 \mid X\subset \bigcup_{y\in Y} B(y,r)\text{ and }Y\subset \bigcup_{x\in X} B(x,r)\big\}. \]

\(d_H(X, Y)=0\) if and only if \(X=Y\).

\(Z=S^1\) is the circle with circumference \(2\pi\)

\[ d_H(X,S^1)=\frac{\pi}{4}. \]

What if the subsets \(X,Y\) have no common embeddding?

Isometric embedding

Definition 4 (The Gromov–Hausdorff Distance) For two abstract metric spaces \((X,d_X)\) and \((Y,d_Y)\), define \[ d_{GH}(X,Y)=\inf d^Z_H(f(X),g(Y)) \]

An Example

Some Properties and Results

  • \(d_{GH}(X,Y)=0\) if and only if \(X\), \(Y\) are isometric

  • \[\tfrac{1}{2}|diam(X)-diam(Y)|\leq d_{GH}(X,Y)\leq \tfrac{1}{2}\max\big\{diam(X), diam(Y)\big\}\]

  • When \(X, Y\) are finite metric spaces

    • Computationally feasible (distortion definition)
    • Minimization problem with exponential search space

  • If \(X,Y\) metric trees, then \(NP\)-hard (Aggarwal et al.)

  • If \(X,Y\subset\mathbb{R}^1\), then \(\frac{5}{4}\)-approximable (Majhi et al.)

  1. Let \((Z,d)\) be a metric space and \(X,Y\subset Z\)
    • \(d^Z_H(X,Y)\) is well-defined
  2. \((X,d)\) and \((Y,d)\) are also metric spaces
    • \(d_{GH}(X,Y)\) can also be defined

How the two distances \(d^Z_H(X,Z)\) and \(d_{GH}(X,Y)\) compare?

  • \(d_{GH}(X,Y)\color{green}{\leq} d_H(X,Y)\)
    • \(Z\) is just one ambient of \(X,Y\)!
  • \(d_{GH}(X,Y) \color{red}{=} d_H(X,Y)\)?

The Circle and A Subset

  • Let \(Z\) be the circle with circumference \(2\pi\)
  • \(X\) be a singleton subset, \(Y=Z\)
  • \(\color{green}{d_H(X,S^1)}=\color{red}{d_{GH}(X,S^1)}=\frac{\pi}{2}\)
  • \(\frac{1}{2}\pi\leq d_{GH}(X,S^1)\leq \frac{1}{2}\pi \implies d_{GH}(X,S^1)=\frac{\pi}{2}\)

The Circle and A Subset

  • \(\color{green}{d_H(X,S^1)}=\frac{\pi}{4}\)
  • \(\frac{1}{2}0\leq \color{red}{d_{GH}(X,S^1)}\leq \frac{1}{2}\pi \implies ?\)
  • One can show that \(d_{GH}(X,S^1)=d_H(X,S^1)\)

The Curious Case of the Circle

\[ \frac{\pi}{3}=\color{red}{d_{GH}(X,S^1)}<\color{green}{d_{H}(X,S^1)}=\frac{\pi}{3}+\varepsilon. \]

Density is The Key

Theorem 1 (DCG 2023) For \(X\subset S^1\) with \(d_H(X,S^1)<\color{red}{\frac{\pi}{6}}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Proof is topological (Vietoris–Rips complex, Nerve Lemma)
  • Is \(\frac{\pi}{6}\) optimal?

Theorem 2 (2024) For \(X\subset S^1\) with \(d_H(X,S^1)<\color{green}{\frac{\pi}{3}}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Proof is purely geometric

Another Perspective: Lower Bound

Corollary 1 (One Subset) Restating Theorem 2, we get \[d_{GH}(X,S^1)\geq\min\big\{d_H(X, S^1),\tfrac{\pi}{3}\big\}.\]

Corollary 2 (Two Subsets) For \(X,Y\subset S^1\) with \(d_H(Y,S^1)\leq\varepsilon\), then \[d_{GH}(X,Y)\geq\min\big\{d_H(X, Y)-2\varepsilon,\tfrac{\pi}{3}-\varepsilon\big\}.\]

  • \(O(n^2)\) lower-bound for \(\max\big\{|X|, |Y|\big\}=n\).

Intuition: when a sample \(X\subset Z\) becomes dense enough, it starts to capture the geometry of the space.

Generally: \(d_{GH}(X,Z)\geq\min\big\{\color{green}{C}\cdot d_H(X, Z), \color{red}{D}\big\}\)?

  • Cirlce: When \(Z=S^1\), then \(\color{green}{C}=1\) and \(\color{red}{D}=\frac{\pi}{3}\).
    • Both are optimal constants

Theorem 3 (Bad News) For any \(\color{green}{C}>0\), there exists a compact metric space \(Z\) and a dense subset \(X\subseteq Z\) with \(d_{GH}(X,Z) < \color{green}{C}\ d_{H}(X,Z)\).

Closed Riemannian Manifolds

One Subset

Theorem 4 (DCG 2023) For \(X\subset M\), we have \[ d_{GH}(X,M)\geq\min\big\{\color{green}{\tfrac{1}{2}}d_H(X, M),\color{red}{\tfrac{\rho(M)}{6}}\big\}. \]

  • \(\color{red}{\rho(M)}\) is the convexity radius of \(M\)
  • The triangle inequality gives us a two subset version
  • \(\color{green}{C}=\frac{1}{2}\) can be improved using Jung’s Theorem

Two Subsets

Theorem 5 (DCG 2023) For \(\color{cornflowerblue}{X},\color{orange}{Y}\subset M\) with \(d(\color{orange}{Y},M)\leq\varepsilon\), we have \[ d_{GH}(\color{cornflowerblue}{X},\color{orange}{Y})\geq\min\big\{\color{green}{\tfrac{1}{2}}d_H(\color{cornflowerblue}{X}, \color{orange}{Y})-\tfrac{3}{2}\varepsilon,\color{red}{\tfrac{\rho(M)}{6}-\tfrac{2}{3}\varepsilon}\big\}. \]

Trees and Graphs

Metric Trees

Theorem 6 (2024) Let \(T\) be a compact tree with finitely edges. For any \(X\subset T\) so that \(d_H(T,X)<\vec{d}_H(\partial T, X)\), we have \[ d_{GH}(X,T)=d_H(X, T). \]

General Graphs

Theorem 7 (2024) Let \(G\) be a compact tree with finite edges. For any \(X\subset G\) so that \(d_H(G,X)<\vec{d}_H(\delta G, X)\), we have \[ d_{GH}(X,G)\geq\min\big\{\color{green}{1}\cdot d_H(X, G),\color{red}{\tfrac{e(G)}{12}}\big\}. \]

  • \(e(G)\) denotes the length of the shortest edge.

Questions

  • For metric graphs, is the density constant \(\frac{e(G)}{12}\) optimal?

    • We conjecture that \(\frac{e(G)}{8}\) should suffice.

  • What about Riemannian manifolds with bounday?

  • Are there classes of metric spaces—other than manifolds and metric graphs—so that \(\color{green}{C}=1\), i.e. \(d_{GH}(X,Z)=d_H(X,Z)\)?

Thank you